package list

// Problem Definition: https://leetcode.com/problems/sort-colors/

func sortColors(nums []int) []int {
	left, right := 0, len(nums)-1
	for i := 0; i <= right; i++ {
		for i <= right && nums[i] == 2 {
			nums[i], nums[right] = nums[right], nums[i]
			right--
		}

		if nums[i] == 0 {
			nums[i], nums[left] = nums[left], nums[i]
			left++
		}
	}

	return nums
}

func sortColors1(nums []int) []int {
	idx := 0
	for num := 0; num <= 1; num++ {
		for i := idx; i < len(nums); i++ {
			if nums[i] == num {
				nums[idx], nums[i] = nums[i], nums[idx]
				idx++
			}
		}
	}
	return nums
}
